package com.arithmetic.list;

/**
 * 链表相关算法
 *
 * @author chenyichang
 * @date 2022/8/7
 */
public class ListArithmetic {

    /**
     * 合并2个递增的链表
     * 如：
     * 链表1==>1,3,4
     * 链表2==>2,5,6
     * 合并后为==>1,2,3,4,5,6
     *
     * @param list1 链表1
     * @param list2 链表2
     * @return
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode result = new ListNode(0);

        ListNode pre1 = list1;
        ListNode pre2 = list2;
        ListNode cur = result;

        while (pre1 != null && pre2 != null) {
            if (pre1.val > pre2.val) {
                cur.next = pre2;
                pre2 = pre2.next;
            } else {
                cur.next = pre1;
                pre1 = pre1.next;
            }
            cur = cur.next;
        }
        //跳出循环，说明至少有一个为null，把不为null的链表加入后面
        if (pre1 != null) cur.next = pre1;
        if (pre2 != null) cur.next = pre2;

        return result.next;
    }

    /**
     * 链表中的节点每k个一组翻转
     * <p>
     * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
     * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
     * 如：1,2,3,4,5
     * k=2 结果为 2,1,4,3,5
     * k=3 结果为 3,2,1,4,5
     *
     * @param head ListNode类
     * @param k    int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        //无须反转的情况
        if (head == null || head.next == null || k < 2) {
            return head;
        }
        //计算head长度，看需要翻转多少次
        ListNode lenNode = head;
        int len = 0;
        while (lenNode != null) {
            len++;
            lenNode = lenNode.next;
        }


        ListNode result = new ListNode(0);
        result.next = head;

        ListNode pre = result;
        ListNode cur = head;

        //执行len/k次翻转
        for (int j = 0; j < len / k; j++) {
            for (int i = 1; i < k; i++) {
                ListNode temp = cur.next;
                cur.next = temp.next;
                temp.next = pre.next;
                pre.next = temp;

            }
            //翻转完成一次，将指针刷新，进行接下来的翻转
            pre = cur;
            cur = cur.next;
        }

        return result.next;
    }

    /**
     * bug写法
     * <p>
     * 反转链表指定位置(不考虑链表只有5个节点，反转位置大于节点数，或者其他异常情况)
     * 比如 1-2-3-4-5 反转2到4的位置
     * 结果:1-4-3-2-5
     * <p>
     * bug1：
     * 如果不设置一个新的node.next = head
     * 有bug  如：{3,5},2,2
     *
     * @param head 链表
     * @param m    反转开始位置
     * @param n    反转结束位置
     * @return 反转后的链表
     */
    private static ListNode reverseBetweenWithBug(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }

        //当前遍历的链表
        ListNode cur = head;

        //前节点   结果返回的是pre.next  ==>  因为pre是一个指针，在随着m变动，所以这里有bug
        ListNode pre = new ListNode();
        pre.next = head;

        //找到m
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }

        //反转m到n的链表
        for (int i = m; i < n; i++) {
            //临时节点
            ListNode temp = cur.next;
            //让当前节点next指向temp的next
            cur.next = temp.next;
            //temp的next 执行pre的next
            temp.next = pre.next;
            //pre的next指向temp
            pre.next = temp;
        }
        return pre.next;
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        //指定一个前置元素 指向该head
        //防止 head链表只有一个元素
        ListNode result = new ListNode();
        result.next = head;

        //前置元素
        ListNode pre = result;//这里pre不能置null  如：{2,3} 1,2===> {3,2}
        //当前元素
        ListNode cur = head;
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        for (int i = m; i < n; i++) {
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return result.next;
    }

    /**
     * 反转链表算法2
     * 无需创建新链表，就移动指针来进行反转（算法参考 {@link ListArithmetic#reverseBetween(ListNode, int, int)}）
     */
    public static ListNode reverse0(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = new ListNode();
        pre.next = head;
        while (head.next != null) {
            ListNode temp = head.next;
            head.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return pre.next;
    }

    /**
     * 反转链表
     * 创建一个空的新链表
     * 遍历链表，摘下第一个元素，将该元素放入新链表的头部位置
     * 最后的新链表即是反转后的链表
     *
     * @param head 需要反转的链表
     * @return 反转后的链表
     */
    public static ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newNode = null;
        //记录当前遍历的链表
        ListNode cur = head;

        while (cur != null) {
            //记录 后面的链表
            ListNode temp = cur.next;
            //把当前节点摘下来 放入新链表
            cur.next = newNode;
            //新链表的指针前移
            newNode = cur;
            //遍历指针后移
            cur = temp;
        }
        return newNode;
    }


}
